中点|升序_算法模板链表

篇首语：本文由编程笔记#小编为大家整理，主要介绍了算法模板-----链表相关的知识，希望对你有一定的参考价值。

链表基础知识点

• null异常的处理
• dummy node节点
• 快慢指针
• 插入一个节点到排序链表
• 从一个链表中移除一个节点
• 反转链表
• 合并两个链表
• 找到链表的中间节点

通过下面的练习&＃xff0c;大部分链表题都能可以应对。
remove-duplicates-from-sorted-list
remove-duplicates-from-sorted-list-ii
reverse-linked-list
reverse-linked-list-ii
merge-two-sorted-lists
partition-list
sort-list
reorder-list
linked-list-cycle
linked-list-cycle-ii
palindrome-linked-list
copy-list-with-random-pointer

常见题型

remove-duplicates-from-sorted-list

给定一个排序链表&＃xff0c;删除所有重复的元素&＃xff0c;使每个元素只出现一次

// 递归
ListNode* deleteDuplicates(ListNode* head)
if(head &＃61;&＃61; NULL || head->next &＃61;&＃61; NULL) return head;
head->next &＃61; deleteDuplicates(head->next);
return head->val &＃61;&＃61; head->next->val ? head->next : head;
// 非递归
ListNode* deleteDuplicates(ListNode* head)
ListNode *cur &＃61; head;
while(cur !&＃61; NULL && cur->next !&＃61; NULL)
if(cur->val &＃61;&＃61; cur->next->val)
cur->next &＃61; cur->next->next; //跳过重复节点
else
cur &＃61; cur->next;


return head;


remove-duplicates-from-sorted-list-ii

给定一个排序链表&＃xff0c;删除所有重复的节点&＃xff0c;只保留原始链表中没有重复出现的。
思路&＃xff1a;链表的头节点可能会被删除&＃xff0c;需要定义一个dummy node辅助进行删除过程
dummy node 的使用在面试中很常见

ListNode* deleteDuplicates(ListNode* head)
if(head &＃61;&＃61; NULL || head->next &＃61;&＃61; NULL) return head;

ListNode *dummy &＃61; new ListNode(-1); //定义dummy node节点进行辅助
dummy->next &＃61; head;
head &＃61; dummy;

int temp;
while(head->next !&＃61; NULL && head->next->next !&＃61; NULL)
if(head->next->val &＃61;&＃61; head->next->next->val)
temp &＃61; head->next->val;
while(head->next !&＃61; NULL && head->next->val &＃61;&＃61; temp)
// 查找所有相同的节点进行删除
head->next &＃61; head->next->next;

else
head &＃61; head->next;


return dummy->next;


注意点&＃xff1a;

• A->B->C 删除B &＃61;> A.next &＃61; C
  删除用一个dummy node节点进行辅助&＃xff08;允许头节点改变&＃xff09;
  访问X.next、X.value一定要保证X!&＃61;NULL&＃xff08;这个很重要&＃xff0c;一定要细心&＃xff09;

reverse-linked-list

反转单链表
思路&＃xff1a;用一个prev节点保存前向指针&＃xff0c;temp保存后向的临时指针。
反转链表的套路要记住&＃xff0c;可能在其他题中会使用

// 迭代
ListNode* reverseList(ListNode* head)
ListNode* pre &＃61; NULL;
ListNode* cur &＃61; head;
while(cur !&＃61; NULL)
ListNode *later &＃61; cur->next;
cur->next &＃61; pre;
pre &＃61; cur;
cur &＃61; later;

return pre;
// 递归
ListNode* reverseList(ListNode* head)
if(head &＃61;&＃61; NULL || head->next &＃61;&＃61; NULL) return head;

ListNode *h &＃61; reverseList(head->next);
head->next->next &＃61; head;
head->next &＃61; NULL;
return h;


reverse-linked-list-ii

反转从位置m到n的链表&＃xff0c;使用一趟扫描完成。(1<&＃61;m<&＃61;n<&＃61;链表长度)
思路&＃xff1a;先遍历到m处&＃xff0c;反转&＃xff0c;再拼接后边的。
需要使用dummy node&＃xff0c;可能会改变head

ListNode* reverseBetween(ListNode* head, int m, int n)
if(head &＃61;&＃61; NULL || head->next &＃61;&＃61; NULL) return head;
ListNode *dummy &＃61; new ListNode(-1);
ListNode *pre &＃61; dummy;
dummy->next &＃61; head;

for(int i &＃61; 0; i pre &＃61; pre->next;


ListNode *cur &＃61; pre->next; // m-1 从此处开始反转
for(int i &＃61; m; i ListNode *temp &＃61; cur->next;
cur->next &＃61; temp->next;
temp->next &＃61; pre->next;
pre->next &＃61; temp;

return dummy->next;


merge-two-sorted-lists

将两个升序链表合并为新的升序链表&＃xff0c;在原链表上进行操作
思路&＃xff1a;定义dummy node&＃xff0c;链接各个元素

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
if(l1 &＃61;&＃61; nullptr) return l2;
if(l2 &＃61;&＃61; nullptr) return l1;

if(l1->val <&＃61; l2->val)
l1->next &＃61; mergeTwoLists(l1->next, l2);
return l1;
else
l2->next &＃61; mergeTwoLists(l1, l2->next);
return l2;



partition-list

分隔链表&＃xff0c;使所有小于x的节点出现在大于或等于x的节点之前。
保留两个分区中每个节点的初始相对位置。
思路&＃xff1a;将大于等于x的节点&＃xff0c;放到另外一个链表中&＃xff0c;最后链接这两个链表

ListNode* partition(ListNode* head, int x)
if(!head) return head;

ListNode *beforeNode &＃61; new ListNode(-1);
ListNode *before &＃61; beforeNode;
ListNode *afterNode &＃61; new ListNode(-1);
ListNode *after &＃61; afterNode;

while(head !&＃61; NULL)
if(head->val before->next &＃61; head;
before &＃61; before->next;
else
after->next &＃61; head;
after &＃61; after->next;

head &＃61; head->next;

after->next &＃61; NULL;
before->next &＃61; afterNode->next;
return beforeNode->next;


当头节点不确定的时候需要使用dummy node

sort-list

在O(nlogn)时间复杂度下&＃xff0c;常数级空间复杂度下&＃xff0c;对链表进行排序(升序)
思路&＃xff1a;使用归并排序&＃xff0c;找中点进行合并操作

ListNode* sortList(ListNode* head)
if(head &＃61;&＃61; NULL || head->next &＃61;&＃61; NULL) return head;

// 使用快慢指针找到中点
ListNode *slow &＃61; head;
ListNode *fast &＃61; head->next;
while(fast !&＃61; NULL && fast->next !&＃61; NULL)
slow &＃61; slow->next;
fast &＃61; fast->next->next;

ListNode *middleNode &＃61; slow->next;
slow->next &＃61; NULL;

ListNode *left &＃61; sortList(head);
ListNode *right &＃61; sortList(middleNode);
return mergeSortList(left, right); // 合并
ListNode* mergeSortList(ListNode* left, ListNode* right)
// 升序合并两个序列
ListNode *dummy &＃61; new ListNode(-1);
ListNode *cur &＃61; dummy;

while(left !&＃61; NULL && right !&＃61; NULL)
if(left->val val)
cur->next &＃61; left;
left &＃61; left->next;
else
cur->next &＃61; right;
right &＃61; right->next;

cur &＃61; cur->next;


while(left !&＃61; NULL) //将剩余的left接在后边
cur->next &＃61; left;
cur &＃61; cur->next;
left &＃61; left->next;


while(right !&＃61; NULL)
// 将剩余的right接在后边
cur->next &＃61; right;
cur &＃61; cur->next;
right &＃61; right->next;


return dummy->next;


注意&＃xff1a;

• 使用快慢指针的时候需要判断fast 及 fast->next 是否为null
• 递归mergeSort需要断开中间节点
• 递归返回条件为head &＃61; null 或者 head.next &＃61; null

reorder-list

给定一个单链表&＃xff0c;L: L0->L1->…->Ln-1->Ln&＃xff0c;将其重新排序为&＃xff1a;L0->Ln->L1->Ln-1…
不能只是单纯改变节点的值&＃xff0c;需要进行节点变换
思路&＃xff0c;找到中间节点&＃xff0c;反转后边部分&＃xff0c;然后合并前后两个链表

void reorderList(ListNode* head)
if(head &＃61;&＃61; nullptr) return;

// 快慢指针找到中点
ListNode *slow &＃61; head;
ListNode *fast &＃61; head->next;
while(fast !&＃61; nullptr && fast->next !&＃61; nullptr)
slow &＃61; slow->next;
fast &＃61; fast->next->next;


ListNode *middleNode &＃61; slow->next;
ListNode *right &＃61; reverseList(slow->next); //反转后边的链表
slow->next &＃61; nullptr;
head &＃61; mergeTwoList(head, right);
ListNode *mergeTwoList(ListNode *left, ListNode *right)
// 合并两个链表
ListNode *dummy &＃61; new ListNode(-1);
ListNode *cur &＃61; dummy;
bool flag &＃61; true; // true: left, false: right
while(left !&＃61; nullptr && right !&＃61; nullptr)
if(flag)
cur->next &＃61; left;
left &＃61; left->next;
else
cur->next &＃61; right;
right &＃61; right->next;

flag &＃61; !flag;
cur &＃61; cur->next;

while(left !&＃61; nullptr)
// 拼接left剩余部分
cur->next &＃61; left;
cur &＃61; cur->next;
left &＃61; left->next;

while(right !&＃61; nullptr)
//拼接right剩余部分
cur->next &＃61; right;
cur &＃61; cur->next;
right &＃61; right->next;

return dummy->next;
ListNode *reverseList(ListNode *root)
//反转链表
ListNode *pre &＃61; nullptr;
ListNode *cur &＃61; root;
while(cur !&＃61; nullptr)
ListNode *temp &＃61; cur->next;
cur->next &＃61; pre;
pre &＃61; cur;
cur &＃61; temp;

return pre;


linked-list-cycle

给定一个链表&＃xff0c;判断是否有环
思路&＃xff1a;快慢指针&＃xff0c;快慢指针相同&＃xff0c;则有环。
如果有环&＃xff0c;在环内每走一步快慢指针距离会减一

bool hasCycle(ListNode* head)
if(head &＃61;&＃61; NULL) return false;

ListNode *slow &＃61; head;
ListNode *fast &＃61; head->next;
while(fast !&＃61; NULL && fast->next !&＃61; NULL)
if(fast &＃61;&＃61; slow) return true;
fast &＃61; fast->next->next;
slow &＃61; slow->next;

return false;


linked-list-cycle-ii

给定一个链表&＃xff0c; 判断入环的第一个节点&＃xff0c;没有环则返回-1。
证明&＃xff1a;
假设链表中环外部分的长度为a&＃xff0c;slow进入环内又走了b的距离与fast相遇&＃xff0c;此时fast已经走完了环的n圈&＃xff0c;因此fast走过的距离为a&＃43;n(b&＃43;c)&＃43;b&＃61;a&＃43;(n&＃43;1)b&＃43;nc。
根据题意&＃xff0c;fast走过的距离使slow走过距离的2倍。则&＃xff1a;
a&＃43;(n&＃43;1)b&＃43;nc&＃61;2(a&＃43;b) &＃61;> a &＃61; c&＃43;(n-1)(b&＃43;c)。
所以当slow与fast相遇时&＃xff0c;我们再额外使用一个指针ptr&＃xff0c;指向链表头部&＃xff0c;随后它与slow每次向后移动一个位置。最终会在入环点相遇。

ListNode* detectCycle(ListNode* head)
if(head &＃61;&＃61; NULL) return head;

ListNode *fast &＃61; head->next;
ListNode *slow &＃61; head;
while(fast !&＃61; NULL && fast->next !&＃61; NULL)
if(fast &＃61;&＃61; slow)
//第一次相遇&＃xff0c;判断有环
//调整slow和fast的步长&＃xff0c;等待第二次相遇
slow &＃61; head;
fast &＃61; fast->next;
while(fast !&＃61; slow)
//第二次相遇 入环口
fast &＃61; fast->next;
slow &＃61; slow->next;

return slow;

fast &＃61; fast->next->next;
slow &＃61; slow->next;

return NULL;


注意&＃xff1a;

• 指针比较时直接比较指针&＃xff0c;不要用值进行比较&＃xff0c;链表中可能存在重复值
• 第一次相遇后&＃xff0c;快指针需要从下一个节点开始和头指针一起匀速运动

另一种方式是fast&＃61;head, slow&＃61;head。

ListNode *detectCycle(ListNode *head)
if(head &＃61;&＃61; NULL) return head;

ListNode *fast &＃61; head;
ListNode *slow &＃61; head;
while(fast !&＃61; NULL && fast->next !&＃61; NULL)
fast &＃61; fast->next->next;
slow &＃61; slow->next;
if(fast &＃61;&＃61; slow)
fast &＃61; head;
while(fast !&＃61; slow)
//第二次相遇就是环的入口
fast &＃61; fast->next;
slow &＃61; slow->next;

return slow;


return NULL;


两个不同点&＃xff1a;

• fast初始化为head.next 则中点在slow.next
• fast初始化为head&＃xff0c;则中点在slow。
  一般使用fast&＃61;head.next较多&＃xff0c;这样可以知道中点的上一个节点&＃xff0c;可以进行删除操作。

palindrome-linked-list

判断一个链表是否是回文链表
找到中点&＃xff0c;反转后边的链表&＃xff0c;前后链表进行比较

bool isPalindrome(ListNode* head)
if(head &＃61;&＃61; NULL) return true;

// 快慢指针找到中点
// 中点是slow->next
ListNode *slow &＃61; head, *fast &＃61; head->next;
while(fast !&＃61; NULL && fast->next !&＃61; NULL)
slow &＃61; slow->next;
fast &＃61; fast->next->next;


ListNode *tail &＃61; reverseList(slow->next);
// 断开两个链表
slow->next &＃61; NULL;
while(head !&＃61; NULL && tail !&＃61; NULL)
if(head->val !&＃61; tail->val) return false;
head &＃61; head->next;
tail &＃61; tail->next;

return true;
ListNode *reverseList(ListNode *head)
// 反转链表
if(head &＃61;&＃61; NULL) return head;
ListNode *pre &＃61; NULL;
while(head !&＃61; NULL)
ListNode *temp &＃61; head->next;
head->next &＃61; pre;
pre &＃61; head;
head &＃61; temp;

return pre;


copy-list-with-random-pointer

给定一个链表&＃xff0c;每个节点包含一个额外增加的随机指针&＃xff0c;该指针指向链表中的任意节点或空节点&＃xff0c;返回这个链表的深拷贝。
思路&＃xff1a;用hash表存储指针&＃xff0c;复制节点跟在原节点的后边。

Node *copyRandomList(Node* head)
if(head &＃61;&＃61; NULL) return head;

// 复制节点跟在原节点后边
// 1->1&＃39;->2->2&＃39;...
Node *cur &＃61; head;
while(cur !&＃61; NULL)
Node *clone &＃61; new Node(cur->val);
clone->next &＃61; cur->next;
cur->next &＃61; clone;
cur &＃61; clone->next;


//处理随机指针
cur &＃61; head;
while(cur !&＃61; NULL)
cur->next->random &＃61; (cur->random !&＃61; NULL) ? cur->random->next : NULL;
cur &＃61; cur->next->next;


// 分离两个链表
cur &＃61; head;
Node *cloneRandom &＃61; cur->next;
while(cur !&＃61; NULL && cur->next !&＃61; NULL)
Node *temp &＃61; cur->next;
cur->next &＃61; cur->next->next;
cur &＃61; temp;

//原始链表头 head
//克隆链表头 cloneRandom
return cloneRandom;